Hello all,

I've been thinking about writing a patch for some time, but only in the past
month have I taken some time to do the research and put one together.  What
I've implemented is a BSP tree data structure that can be used in place of
the bounding volumes/light buffer/vista buffer to improve raytracing
performance.  The premise is that for scenes with many objects, a lot of
time is spent sorting the bounding box intersections from front to back,
and intersecting bounding boxes that may later be discarded.  With a
spatial subdivision like a BSP tree that partitions *space* instead of
*objects*, there is no need for a sort on the length of the ray, as the
space can be efficiently traversed in order, and few additional bounding
box intersections are required than those in front of the final object
intersection.

I've put together the patch as a set of diffs (following the example of the
previous patch posted here).  The patch can be found at
http://povplace.addr.com/bsppov.tar.gz

Since many people will not be able to make heads or tails of what to do with
(the diffs), I am working on a Windows binary.

There is some more information about the performance improvements on scenes
included with POV-Ray in the README file in the package.  In general, the
patch produces the largest performance gain on scenes with large numbers of
simple-to-intersect objects (as high as 70% improvement).  I have not
observed a scene that renders slower with the new data structure.

There is still lots of room for optimization for the patch, and I am working
on having it work on objects with some internal structure like meshes.

Andrew Clinton

Post a reply to this message